1680D - Dog Walking - CodeForces Solution

// Problem: D. Dog Walking
// Contest: Codeforces - Educational Codeforces Round 128 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1680/problem/D
// Memory Limit: 256 MB
// Time Limit: 4000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>

#define uint unsigned int
#define LL long long
#define ull unsigned long long
#define lll __int128
#define Rtype int
#define mp make_pair
#define pb emplace_back
#define fi first
#define se second
#define priq priority_queue

 #define FREAD
 #define FWRITE

#define Memcost (to_string(fabs((&MenM)-(&MstM))/1024.0/1024.0)+" MiB")
#define Timcost (check(clock()))
bool MstM;

using namespace std;


// mt19937 gen(chrono::system_clock::now().time_since_epoch().count());
// uniform_int_distribution<Rtype>Random(1,n);
template<class T>T Abs(T a){return a<0?-a:a;}
template<class T,class T2>T mmin(T a,T2 b){return a<b?a:b;}
template<class T,class T2>T mmax(T a,T2 b){return a>b?a:b;}
template<class T,class ...T2>T mmin(T a,T2 ...b){return mmin(a,mmin(b...));}
template<class T,class ...T2>T mmax(T a,T2 ...b){return mmax(a,mmax(b...));}
template<class T>T gcd(T a,T b){if(!b||!a)return a+b;if(a<0)a=-a;while(b^=a^=b^=a%=b);return a;}
template<class T,class T2>T gcd(T a,T2 b){if(!b||!a)return a+b;if(a<0)a=-a;while(b^=a^=b^=a%=b);return a;}


namespace IO{
	const int SIZE=1<<20;
	struct ioReader{
		char Buf[1<<20];
		#ifdef FREAD
		char buf[SIZE],*p1,*p2;
		#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,stdin),p1==p2)?EOF:*p1++)
		#else
		#define gc getchar
		#endif
		template<class T>void read(T &x)
		{
			x=0;
			char ch=gc();bool f=ch=='-';
			while(ch<'0'||ch>'9')ch=gc(),f|=ch=='-';
			while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=gc();
			if(f)x=-x;
		}
		void read(char &x)
		{
			x=gc();
			while(isspace(x))x=gc();
		}
		void read(char* x)
		{
			#ifdef FREAD
			char ch=gc();
			while(isspace(ch)&&ch!=EOF)ch=gc();
			while(!isspace(ch)&&ch!=EOF)*(x++)=ch,ch=gc();
			*x='\0';
			#else
			scanf("%s",x);
			#endif
		}
		void read(string &x)
		{
			read(Buf);
			x=Buf;
		}
		#define redReal(type) \
		void read(type &x){ \
			x=0.0; \
			char ch=gc();bool f=ch=='-'; \
			while((ch<'0'||ch>'9')&&ch!='.')ch=gc(),f|=ch=='-'; \
			while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=gc(); \
			if(ch=='.') \
			{ \
				ch=gc(); \
				type p=0.1; \
				while(ch>='0'&&ch<='9')x+=p*(ch-'0'),ch=gc(),p*=0.1; \
			} \
			if(f)x=-x; \
		}
		redReal(float) redReal(double) redReal(long double)
		template<class T1,class ...T2>void read(T1&x,T2&...y)
		{
			read(x);
			read(y...);
		}
		template<class T>void operator()(T &x){read(x);}
		template<class T,class ...T1>void operator()(T &x,T1 &...y){read(x);read(y...);}
	}red;
	template<uint debug>struct ioWriter{
		#define To (debug==1?stdout:stderr)
		const int Fixed=6;
	//	const int Fixed=8;
		#ifdef FWRITE
		char outbuf[SIZE],*p3=outbuf;
		#define pc(x) (p3-outbuf==SIZE?fwrite(outbuf,1,SIZE,To),p3=outbuf,*p3++=x:*p3++=x)
		#else
		#define pc(x) (debug==1?putchar(x):fprintf(stderr,"%c",x))
		#endif
		template<class T>void print(T x)
		{
			if(x<0)x=-x,pc('-');
			int stack[35],cnt=0;
			do{
				stack[cnt++]=x%10;x/=10;
			}while(x);
			while(cnt)pc(stack[--cnt]+'0');
		}
		void print(char x){pc(x);}
		void print(const char *x){int len=strlen(x);for(int i=0;i<len;i++)pc(x[i]);}
		void print(char *x){int len=strlen(x);for(int i=0;i<len;i++)pc(x[i]);}
		void print(string x){int len=x.size();for(int i=0;i<len;i++)pc(x[i]);}
		#define writeReal(type) \
		void print(type x) \
		{ \
			if(x<0)pc('-'),x=-x; \
			int newx=int(x); \
			print(newx);x-=newx;pc('.'); \
			for(int i=1;i<=Fixed;i++)x=x*10,newx=int(x),print(newx),x-=newx; \
		}
		writeReal(float) writeReal(double) writeReal(long double)
		template<class T1,class ...T2>void print(T1 x,T2 ...y)
		{
			print(x);
			print(y...);
		}
		template<class T>void operator()(T x){print(x);}
		template<class T,class ...T1>void operator()(T x,T1 ...y){print(x);print(y...);}
		#undef To
	};
	ioWriter<1>print;
}
using IO::red,IO::print;

#ifndef ONLINE_JUDGE
#define eprintf(...) {fprintf(stderr,__VA_ARGS__);fflush(stderr);}
#include "src/Mydebug.h"
#else
#define debug(...) 42
#define eprintf(...) 42
#endif

constexpr int N=3e3+5,M=1e6+5,INF=0x7f7f7f7f,Mod=1e9+7;
constexpr double eps=1e-8,Pi=acos(-1.0);
typedef pair<int,int> pi;
typedef pair<int,pair<int,int>> pii;

int n,cnt[N];
LL k,v[N],sum[N],ans;
bool MenM;
int main()
{
	#ifdef file
	freopen("data.in","r",stdin);
	freopen("my.out","w",stdout);
	#endif
	red(n,k);
	for(int i=1;i<=n;i++)red(v[i]),cnt[i]=cnt[i-1]+(!v[i]),sum[i]=sum[i-1]+v[i];
	if(abs(sum[n])>k*cnt[n]){puts("-1");return 0;}
	for(int l=1;l<=n;l++)
		for(int r=l;r<=n;r++)
		{
			LL ssum=sum[r]-sum[l-1],scnt=cnt[r]-cnt[l-1];
			ans=mmax(ans,mmin(abs(ssum+k*scnt),abs(sum[n]-ssum-k*(cnt[n]-scnt))),mmin(abs(ssum-k*scnt),abs(sum[n]-ssum+k*(cnt[n]-scnt))));
		}
	print(ans+1,'\n');
	debug(Timcost,Memcost);
	#ifdef FWRITE
		#ifndef ONLINE_JUDGE
		fwrite(eprint.outbuf,1,eprint.p3-eprint.outbuf,stderr);
		#endif
	fwrite(IO::print.outbuf,1,IO::print.p3-IO::print.outbuf,stdout);
	#endif
	return 0;
}